package vip.zhenzicheng.algorithm.demo.sum;

/**
 * 前缀和 arr[] = ? 频繁查找从[L-R)上的元素和 暂时不考虑边界条件
 * 解法1：直接sum(L,R) 不推荐！
 * 解法2：生成二维数组[0-R][0-L]，然后sum(L,R)==[L][R]
 * 解法3：生成前缀和数组 [i] = [0]+[1]+...+[i]，sum(L,R) == [R] - [L]
 *
 * @author zhenzicheng
 * @date: 2022-05-17 09:48
 */
public class PreSum {
  public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    RangeSum1 sum1 = new RangeSum1(arr);
    System.out.println(sum1.rangeSum(2, 8));

    RangeSum2 sum2 = new RangeSum2(arr);
    System.out.println(sum2.getResult(2, 8));

    RangeSum3 sum3 = new RangeSum3(arr);
    System.out.println(sum3.rangeSum(2, 8));

  }

  private static class RangeSum1 {
    private final int[] arr;

    public RangeSum1(int[] arr) {
      this.arr = arr;
    }

    public int rangeSum(int L, int R) {
      int sum = 0;
      for (int i = L; i < R; i++) {
        sum += arr[i];
      }
      return sum;
    }
  }

  /**
   * 二维结果表
   */
  private static class RangeSum2 {
    private final int[] arr;
    private int[][] result;

    public RangeSum2(int[] arr) {
      this.arr = arr;
      transform();
    }

    private void transform() {
      if (this.arr == null) {
        return;
      }
      int N = arr.length;
      // init
      result = new int[N][N];
      for (int end = 0; end < N; end++) {
        for (int i = 0; i < N; i++) {
          if (i == end) {
            result[i][i] = arr[i];
          } else {
            result[end][i] = rangeSum(end, i);
          }
        }
      }
    }

    public int getResult(int L, int R) {
      return result[L][R];
    }

    private int rangeSum(int L, int R) {
      int sum = 0;
      for (int i = L; i < R; i++) {
        sum += arr[i];
      }
      return sum;
    }

  }

  /**
   * 一维前缀和数组
   */
  private static class RangeSum3 {
    private int[] arr;

    public RangeSum3(int[] array) {
      int N = array.length;
      arr = new int[N];
      arr[0] = array[0];
      for (int i = 1; i < N; i++) {
        arr[i] = arr[i - 1] + array[i];
      }
    }

    private int rangeSum(int L, int R) {
      return L == 0 ? arr[R] : arr[R - 1] - arr[L - 1];
    }
  }

}
